/**
 * 一家公司拥有 M 名开发同学以及 N 名产品同学，每位员工有各自的技能等级（一个正整数），表示为一个整数
 * 数组 skills，但技能越高费用越高。
 * 公司计划启动 N 个项目（N <= M），每个项目需要指定至少一位开发同学以及一位产品同学，且每个项目的难
 * 度等级已知（一个正整数，最大不会超过 M 以及 N 之中的技能等级），表示为一个整数数组 project_difficulties。编
 * 写一个程序，输入技术同学技能数组 developer_skills 、产品同学技术数据 product_skills 以及项目难度数组
 * project_difficulties，输出一个有效的项目分配方案，使得公司在这些项目上的投入费用最低。
 * 要求：
 * ● 每位同学均可以负责多个项目，但最多负责 2 个项目；
 * ● 每个项目需要指定至少一位开发同学以及一位产品同学；
 * ● 员工负责项目的难度不能超过其自身的技能等级。
 * ● 公司的目标是总技能等级之和最优。
 * 数组格式可以参考：
 * developer_skills：[A：1，B：2，C：3...]
 * product_skills：[a：1，b：2，c：3...]
 * project_difficulties：[project1：1，project2：2，project3：3...]
 */


import java.util.ArrayList;
import java.util.List;

/**
 * 分析：从题中描述可知这里产品经理数量和项目数量是相等的都是N，开发者数量是一定>=N的M。
 * 那么产品经理和开发者可以分开统计。
 * 目标是总技能等级之和最优：即满足投入工作的开发同学和产品同学的技能之和最小即可。
 * 依据成本最低原则，应该将能力达到项目难度的开发同学和产品同学优先进行分配，并且要尽量为已分配岗位的同学充分安排两份工作已降低成本。
 *
 */

public class Main {
    public static void main(String[] args) {
        //自定义开发、产品、项目的能力和难易度
        //developer_skills：开发者能力数列
        int[] developer_skills = {5,5,5,3,4,5};
        int[] product_skills = {1,2,3,2,4};
        int[] project_difficulties = {1,2,3,2,4};
        int M = developer_skills.length;
        int N = product_skills.length;

        //首先判断产品数量和项目数量是否相等
        if(product_skills.length!=project_difficulties.length){
            System.out.println("错误：产品经理数量和项目数量不相等，请确认输入数据");
        }
        //按照从小到大对开发、产品、项目的能力和难易度进行排序
        choiceSort(developer_skills);
        choiceSort(product_skills);
        choiceSort(project_difficulties);

        //转化成列表
        List<Integer> prodectList = new ArrayList<>();
        List<Integer> developerList = new ArrayList<>();
        for (int i = 0; i < product_skills.length; i++) {
            prodectList.add(product_skills[i]);
        }
        for (int i = 0; i < developer_skills.length; i++) {
            developerList.add(developer_skills[i]);
        }

        List listProduct = getSkillList(prodectList,project_difficulties);
        if(listProduct==null){
            System.out.println("错误：匹配失败");
        }
        int res=0;
        List listDeveloper = getSkillList(developerList,project_difficulties);
        if(listDeveloper==null){
            System.out.println("错误：匹配失败");
        }
        System.out.println("分配结果：");
        System.out.print("开发同学: [");
        for (int i = 0; i < listDeveloper.size(); i++) {
            res+=(int)listDeveloper.get(i);
            System.out.print(listDeveloper.get(i)+" ");
        }
        System.out.println("]");

        System.out.print("产品同学: [");
        for (int i = 0; i < listProduct.size(); i++) {
            res+=(int)listProduct.get(i);
            System.out.print(listProduct.get(i)+" ");
        }
        System.out.println("]");

        System.out.println("总数是："+res);

    }

    private static List getSkillList(List<Integer> skills, int[] projectDifficulties) {
        List<Integer> list = new ArrayList<>();
        for (int i = projectDifficulties.length-1; i >=0 ; i--) {
            int index = skills.size()-1;
            if(skills.get(index)<projectDifficulties[i]){
                System.out.println("同学能力与项目难度不匹配");
                return null;
            }
            //筛选最低满足项目难度的能力者
            while(index>=0&&skills.get(index)>=projectDifficulties[i]){
                index--;
            }
            //此时最低满足项目难度的能力者是skills[index+1]
            index++;
            list.add(skills.get(index));
            //如果还有项目，优先将已经投入的同学防置进去
            if(i>0){
                list.add(skills.get(index));
                i--;
            }
            //清理同学列表中已经投入项目的人员
            skills.remove(index);
        }
        return list;
    }

    private static void choiceSort(int[] num) {
        for (int i = 0; i < num.length; i++) {
            for (int j = i+1; j < num.length; j++) {
                if(num[i]>num[j]){
                    swap(num,i,j);
                }
            }
        }
    }
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}